package org.example.everyday;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/23 10:54
 */
public class Lc1994 {
    //30以内的10个质数
    int[] primes = {2,3,5,7,11,13,17,19,23,29};
    //30以内需要排除的数字
    int[] bads = {4,25,9};
    //防止溢出的取模基数
    int MOD = 1000000007;

    /** dp[i] 好子集的个数 状态dp[i] i对应互不相同的质数的乘机，
     dp[i]好子集的个数 转移方程：考虑num,num所有质因数还没有被用过（getMask(num) & preMask ==0）
     更新bitmask和dp (dp[getMask(num) | preMask]) += dp[preMask] * cnt(num)) 初始化 dp[0] = 1
     结果：sum(dp[i]) bitmask: num1 ,num2 getMask(num1) & getMask(num2) > 0,
     说明有相同的质数；如果等于0，说明没有 */
    public int numberOfGoodSubsets(int[] nums) {
        int[] cnt = count(nums);

        //dp 一共有1<<10种可能性，
        long[] dp = new long[1 + (1 << 10)];
        //初始化dp 第一个元素
        dp[0] = 1L;

        //转移方程
        for(int num = 2; num <= 30; num++){
            if(cnt[num] == 0 || isBadNum(num)){
                continue;
            }
            //获取每个数的bitmask
            int numMask = getMask(num);
            for(int preMask = 0; preMask < (1 << 10); preMask++){
                if((preMask  & numMask) > 0){
                    continue;
                }
                //转移dp
                dp[preMask | numMask] += dp[preMask] * cnt[num];
                dp[preMask | numMask] %= MOD;
            }
        }

        return getAns(dp,cnt);

    }

    private int getAns(long[] dp,int[] cnt){
        long ans = 0;
        for(int i = 1; i < (1 << 10); i++){
            ans += dp[i];
            ans %= MOD;
        }
        /**
         这里为什么要用cnt[1],而不用cnt[2],cnt[3]...呢？
         因为数字1要特殊处理一次，因为1既不是质数，但是又不影响最终组合的数量，所以要把动态规划中已经算好的组合 在考虑 加上1组成的组合；
         比如 给的cnt= [2,3] 组合是3个，[2],[3],[2,3],但是如果cnt = [1,2,3], 那么组合会变成
         [2],[3],[2,3],[1,2],[1,3],[1,2,3]  相当于在在前组合的基础上都加了一个1。所以这里要判断数组中是否包含1
         */
        ans *= pow(2L,cnt[1]);
        ans %= MOD;

        return (int)ans;
    }

    /**
     快速幂的算法
     */
    private long pow(long base,int k){
        long ans = 1L;
        while(k > 0){
            if(k % 2 ==1){
                ans = (ans * base) % MOD;
            }
            base = (base * base) % MOD;
            k >>= 1;
        }
        return ans;
    }

    /**
     获取每个数字的二进制mask,这个都是自己定义的
     [2,3,5,7]

     */
    private int getMask(int num){
        int ans = 0;
        for(int i = 0; i< 10; i++){
            if(num % primes[i] == 0){
                ans += (1 << i);
            }
        }
        return ans;
    }


    /**
     判断一个数是不是坏的数字
     */
    private boolean isBadNum(int num){
        for(int b : bads){
            if(num % b == 0){
                return true;
            }
        }
        return false;
    }

    /**
     获取数组中的元素出现的个数
     */
    private int[] count(int[] nums){
        int[] ans = new int[31];
        for(int n : nums){
            ans[n]++;
        }
        return ans;
    }

    public static void main(String[] args) {
        Lc1994 lc1944 = new Lc1994();
//        int[] nums = {2,3,5};
        int [] nums = {10,11,5,1,10,1,3,1,26,11,6,1,1,15,1,7,22,1,1,1,1,1,23,1,29,5,6,1,1,29,1,1,21,19,1,1,1,2,1,11,1,15,1,22,14,1,1,1,1,6,7,1,14,3,5,1,22,1,1,1,17,1,29,2,1,15,10,1,5,7,1,1,1,30,1,30,1,21,10,1,1,1,1,1,2,6,5,7,3,1,1,19,29,1,7,13,14,1,5,26,19,11,1,1,1,1,1,1,1,1,22,15,1,1,13,1,17,1,1,1,13,6,1,10,1,1,17,1,1,3,14,7,17,1,13,1,1,1,1,1,11,1,1,6,1,1,1,1,1,2,1,30,2,26,1,1,14,1,26,29,30,1,13,21,1,1,14,21,1,23,1,15,23,21,1,30,19,19,1,10,23,3,3,17,22,2,26,1,11,1,23,1,1,1,15,1,1,13,1,1};
        int result = lc1944.numberOfGoodSubsets(nums);
        System.out.println(result);

//        for (int i = 0; i < PRIMES.length; i++) {
//            int num = PRIMES[i];
//            int result1 = lc1944.getMask(num);
//            System.out.println("getMask="+result1);
//        }

//        lc1944.pow(2L,3);

    }


}
